#include <iostream>
#include <string>
#include <cmath>
#include <ctime>

using namespace std;
struct SkipListNode
{
    static int count;
    int key;
    int data;
    int level;//层高

    SkipListNode**  next_nodes;//Node*数组
    SkipListNode()
    {
        //cout<<"create "<<++count<<" node "<<endl;
    }
    ~SkipListNode()
    {
        //cout<<"left "<<--count<<" node "<<endl;
    }
};

int SkipListNode::count = 0;
/*
 * 1    head-----------------> node2 ----------------> tail
 *
 * 0    head ----> node1 ----> node2 ----> node3 ----> tail
 *
 * */
class SkipList
{
    int             MAX_LEVEL;
    SkipListNode*   head;
    SkipListNode*   tail;
    int*            plevelnum;

public:
    SkipList(int maxlevel);
    ~SkipList();
    int RandomLevel();
    void Insert(int key,int data);
    SkipListNode*   Find(int key);
    void Print();
};

SkipList::SkipList(int maxlevel):MAX_LEVEL(maxlevel)
{
    head = new SkipListNode;
    tail = new SkipListNode;

    head->level = maxlevel;
    head->next_nodes = new SkipListNode*[maxlevel];
    for (int i = 0; i < maxlevel; ++i)
    {
        head->next_nodes[i] = tail;
    }
    plevelnum = new int[MAX_LEVEL];
    bzero(plevelnum, sizeof(int)*MAX_LEVEL);
}

SkipList::~SkipList()
{
    SkipListNode* curr = head;
    while (head != tail)
    {
        curr = head->next_nodes[0];
        delete[] head->next_nodes;
        delete head;
        head = curr;
    }
    delete tail;
    delete[] plevelnum;
}

int SkipList::RandomLevel()
{
    int level = 0;
    while(rand()%2 && level < MAX_LEVEL -1)
        ++level;
    return level;
}

void SkipList::Insert(int key,int data)
{
    SkipListNode* curr = head;
    SkipListNode** update = new SkipListNode*[MAX_LEVEL];
    int top_level = MAX_LEVEL - 1;
    for(int i = top_level ; i >= 0 ; --i)
    {
        if(curr->next_nodes[i] == tail || curr->next_nodes[i]->key > key)
        {
            //记录即将插入新节点的前驱节点
            update[i] = curr;
        }
        else
        {
            //一直找到前驱节点
            while(curr->next_nodes[i] != tail && curr->next_nodes[i]->key < key)
                curr = curr->next_nodes[i];
            //如果是同一个key,更新值
            if(curr->next_nodes[i] != tail && curr->next_nodes[i]->key == key)
            {
                curr->next_nodes[i]->data = data;
                return;
            }
            update[i] = curr;
        }
    }
    //创建节点
    SkipListNode* node = new SkipListNode;
    node->key = key;
    node->data = data;
    node->level = RandomLevel()+1;

    //记录每一层的节点数
    for (int k = 0; k < node->level; ++k)
    {
        plevelnum[k] += 1;
    }

    //cout<<"key = "<<key<<" level = "<<node->level<<endl;
    node->next_nodes = new SkipListNode*[node->level];

    for (int j = 0; j < node->level; ++j)
    {
           node->next_nodes[j] = update[j]->next_nodes[j];
           update[j]->next_nodes[j] = node;
    }
    delete[] update;
}

SkipListNode* SkipList::Find(int key)
{
    int toplevel = MAX_LEVEL - 1;
    SkipListNode* curr = nullptr;
    SkipListNode* pre = head;
    while(toplevel >= 0)
    {
        curr = pre->next_nodes[toplevel];
        while(curr != tail)
        {
            if(curr->key == key)
            {//找到返回
                return curr;
            }
            if(key > curr->key)
            {//大于当前节点,向后继续查找
                pre = curr;
                curr = curr->next_nodes[toplevel];
            }
            else
            {
                break;
            }
        }
        //进入下一层
        toplevel--;
    }

    return nullptr;
}

void SkipList::Print()
{
    string* line = new string[MAX_LEVEL];
    SkipListNode* curr = head->next_nodes[0];
    for (;curr != tail; curr = curr->next_nodes[0])
    {
        for (int i = 0; i < MAX_LEVEL; ++i)
        {
            if(curr->level > i)
            {
                line[i] += to_string(curr->key)+"\t";
            }
            else
            {
                line[i] += "\t";
            }

        }
    }
    for (int j = 0; j < MAX_LEVEL; ++j)
    {
        cout<<line[j]<<endl;
    }
    for (int k = 0; k < MAX_LEVEL; ++k)
    {
        cout<<"level = "<<k<<" num = "<<plevelnum[k]<<endl;;
    }
}

int main()
{
    srand(time(0));
    SkipList slist(4);

    for (int i = 0; i < 50; ++i)
    {
        slist.Insert(rand()%100,10);
        //slist.Insert(i,10);
    }
    slist.Print();

    int fid = rand()%100;
    SkipListNode* result = slist.Find(fid);
    if(result == nullptr)
    {
        cout<<"找不到 key = "<<fid<<endl;
    }
    else
    {
        cout<<"level = "<<result->level<<" key = "<<result->key<<" data = "<<result->data<<endl;
    }
//    slist.Insert(rand()%1000,10);
//    slist.Print();
    return 0;
}